package swardToOffer.struct_1_arr;

/**
 * @Author ChanZany
 * @Date 2021/5/24 20:06
 * @Version 1.0
 * <p>
 * 面试题45：把数组排成最小的数
 * 题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼
 * 接出的所有数字中最小的一个。例如输入数组{3, 32, 321}，则打印出这3个数
 * 字能排成的最小数字321323。
 * <p>
 * 方法1:全排列+求排列中的MIN,数字太大.还很麻烦
 * 方法2:自定义排序
 * 两个数字x和y,若xy>yx,则x"大于"y,反之x"小于"y
 * 排序完成后,数组中"小"的数字应该在"大"的数字的左边;
 */
public class SortArrayForMinNumber {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        //自定义排序
        quickSort(strs, 0, strs.length - 1);
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }

    private void quickSort(String[] strs, int left, int right) {
        if (left >= right) return;
        int i = left, j = right; //strs[left] is base
        String tmp = strs[i];
        while (i < j) {
            while ((strs[j] + strs[left]).compareTo(strs[left] + strs[j]) >= 0 && i < j) j--;
            while ((strs[i] + strs[left]).compareTo(strs[left] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        //i,j encounter
        strs[i] = strs[left];
        strs[left] = tmp;
        quickSort(strs, left, i - 1);
        quickSort(strs, i + 1, right);
    }

    public static void main(String[] args) {
        SortArrayForMinNumber Main = new SortArrayForMinNumber();
        Main.minNumber(new int[]{1, 2, 3});
    }
}
